package com.yun.algorithmproblem.leetcode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class Leetcode895 {
    static class FreqStack {

        HashMap<Integer, Integer> frequencyMap;
        HashMap<Integer, LinkedList<Integer>> listMap;

        int max = 1;

        public FreqStack() {
            frequencyMap = new HashMap<>();
            listMap = new HashMap<>();
        }

        public void push(int val) {
            int f=frequencyMap.getOrDefault(val,0)+1;
            frequencyMap.put(val,f);
            if(f>max){
                max=f;
            }
            listMap.computeIfAbsent(f,v->new LinkedList<>()).push(val);
        }

        public int pop() {
            LinkedList<Integer> list = listMap.get(max);
            int pop = list.pop();
            frequencyMap.put(pop,frequencyMap.get(pop)-1);
            if(list.size()==0){
                max--;
            }
            return pop;
        }

        private void printFrequencyMap(HashMap<Integer, Integer> frequencyMap) {
            System.out.println("frequencyMap");
            for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
                System.out.println(entry.getKey() + "," + entry.getValue());
            }
        }

        private void printListMap(HashMap<Integer, LinkedList<Integer>> listMap) {
            System.out.println("listMap");
            for (Map.Entry<Integer, LinkedList<Integer>> entry : listMap.entrySet()) {
                System.out.print(entry.getKey() + "->");
                System.out.println(entry.getValue());
            }
        }
    }

    public static void main(String[] args) {
        FreqStack obj = new FreqStack();
        obj.push(5);
        obj.push(7);
        obj.push(5);
        obj.push(7);
        obj.push(4);
        obj.push(5);
        obj.pop();
        obj.pop();
        obj.pop();
        obj.pop();
    }
}
